#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
const int maxn = 1e5;

struct node {
	int point, dis;
	bool operator < (const node &x) const {
		return dis > x.dis;
	}
};


int dist[maxn + 5];
vector<pii> edge[maxn + 5];
priority_queue<node> q;
bool vis[maxn + 5];


inline void dijkstra(int s) {
	memset(dist, 0x3f, sizeof(dist));
	dist[s] = 0;
	q.push({s, 0});

	while (!q.empty()) {
		node t = q.top();
		q.pop();

		if (vis[t.point]) continue;
		vis[t.point] = 1;

		for (auto ii : edge[t.point]) {
			dist[ii.first] = min(dist[ii.first], dist[t.point] + ii.second);

			if (!vis[ii.first])
				q.push({ii.first, dist[ii.first]});
		}
	}
}


signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, m, s;
	cin >> n >> m >> s;

	int x, y, z;
	for (int i = 1; i <= m; i++) {
		cin >> x >> y >> z;
		edge[x].push_back({y, z});
	}

	dijkstra(s);

	for (int i = 1; i <= n; i++) {
		cout << dist[i] << " ";
	}
	return 0;
}
